package 剑指offer.Month7_07.day12;

public class 矩阵中的路径 {
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        char[] arr = word.toCharArray();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if(dfs(matrix,arr,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] matrix,char[] arr,int i,int j,int index){
        if(i >= matrix.length || i < 0 || j >= matrix[0].length || j < 0 || matrix[i][j] != arr[index]){
            return false;
        }

        if(index == arr.length - 1) return true;
        char tmp = matrix[i][j];
        matrix[i][j] = ' ';
        boolean flag =  dfs(matrix,arr,i - 1,j,index + 1) ||
                dfs(matrix,arr,i + 1,j,index + 1) ||
                dfs(matrix,arr,i,j - 1,index + 1) ||
                dfs(matrix,arr,i,j + 1,index + 1);
        matrix[i][j] = tmp;
        return flag;
    }
}
